package listbyorder.access001_100.test14;

/**
 * 前缀树解法---自己的解法
 * @author code_yc
 * @version 1.0
 * @date 2020/5/27 0:01
 */
public class Solution2 {

    // 方法二：前缀树求解
    public String longestCommonPrefix2(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        // 创建前缀树
        TrieTree tree = new TrieTree();
        for (String str : strs) {
            tree.add(str);
        }
        int len = strs.length;
        return tree.getMaxPrefix(strs[0], len);
    }

    // 创建节点类
    class Node {
        int path;
        int end;
        Node[] next;

        public Node() {
            next = new Node[26];
        }
    }

    // 创建前缀树的类
    class TrieTree {
        Node root;

        public TrieTree() {
            this.root = new Node();
        }

        // 向前缀树种添加元素
        void add(String s) {
            char[] chars = s.toCharArray();
            Node temp = root;
            int cur = 0;
            for (char c : chars) {
                cur = c - 'a';
                if (temp.next[cur] == null) {
                    temp.next[cur] = new Node();
                }
                temp = temp.next[cur];
                temp.path++;
            }
            temp.end++;
        }

        // 检查当前最大前缀
        String getMaxPrefix(String s, int len) {
            String res = "";
            Node temp = root;
            char[] chars = s.toCharArray();
            int cur = 0;
            for (char c : chars) {
                cur = c - 'a';
                temp = temp.next[cur];
                if (temp.path != len) {
                    break;
                } else {
                    res += c;
                }
            }
            return res;
        }
    }
}
